package priv.mill.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 二分查找代码
 * 
 * @author mill
 *
 */
public class ErFenSearch {

	public static void main(String[] args) {
		ErFenSearch erFenSearch = new ErFenSearch();
		Random random = new Random(47);
		for (int i = 0; i < 100; i++) {
			erFenSearch.add(random.nextInt(1000));
		}
		erFenSearch.print();
		erFenSearch.sort();
		erFenSearch.print();
		
		int search = erFenSearch.search(998);
		System.out.println(search);
	}


	public int search(long i) {
		int l=0,h=arr.length-1;
		while(true) {
			int mid = (l+h)/2;
			if(arr[mid]==i)
				return mid;
			else if(l>h)
				return -1;
			else {
				if(arr[mid]>i) {//小了
					h=mid-1;
				}else {
					l=mid+1;
				}
			}
		}
	}

	public void sort() {
		questSort(0,index-1);
	}

	private void questSort(int l, int r) {
		if(r-l<=0) {
			return;
		}else {
			long tem = getMid(l,r); // 参考值
			int m = huaFen(l,r,tem); //划分大的到右边小的到左边
			questSort(l,m-1); //分治算法
			questSort(m+1,r);
		}
	}


	private long getMid(int l, int r) {
		int center = (l+r)/2;
		if(arr[center]>arr[r])
			warp(center,r);
		if(arr[l]>arr[center])
			warp(l,center);
		if(arr[l]>arr[r])
			warp(l,r);
		warp(center,r-1);
		return arr[r-1];
	}


	private int huaFen(int l, int r, long tem) {
		int left = l;//之后 ++
		int right = r-1;
		while(true) {
			while(arr[++left]<tem);
			while(right>0 && arr[--right]>tem);
			if(left>right)
				break;
			else
				warp(left, right);
		}
		warp(r, left);
		return left;
	}


	private void insertSort() {
		int in,out;
		long temp;
		int h=1;//间隔
		while(h<index/3) { //找到最大间隔
			h*=3;
			h++;
		}
		while (h>0) { // 不断缩小间隔
			for (out = h; out < index; out++) {
				temp = arr[out];
				in = out;
				while (in > h - 1 && arr[in - h] >= temp) {//arr[in-1]<temp则找到了为止
					arr[in] = arr[in - h];
					in -= h;
				}
				arr[in] = temp;
			} 
			h=(h-1)/3;
		}
	}


	private void bubbleSort() {
		int out,in;
		for(out=arr.length-1;out>0;out--) {
			for(in=0;in<out;in++) {
				if(arr[in]>arr[in+1]) {
					warp(in,in+1);
				}
			}
		}
	}
	private void selectSort() {
		int out,in,min=0;
		for(out=0;out<index-1;out++) {
			min=out;
			for(in=out+1;in<index;in++) {
				if(arr[in]<arr[min]) {
					min=in;
				}
			}
			warp(out,min);
		}
	}


	private void warp(int a, int b) {
		long temp = arr[a];
		arr[a]=arr[b];
		arr[b]=temp;
	}


	public void print() {
		System.out.println(Arrays.toString(arr));
	}

	private int index;
	private long[] arr = new long[100];

	public void add(long value) {
		this.arr[index++] = value;
	}

}
